#include<bits/stdc++.h>
using namespace std;
#define int long long
int m = 0;
const int N = 1e6+10;
int minP[N];
int pi[N];
vector<int> p;
void pre(){
    for(int i = 2;i<=m;i++){
        if(!minP[i]){
            minP[i] = i;
            p.push_back(i);
        }
        for(int j = 0;p[j] != minP[i] && 1ll*p[j]*i <= m;j++){
            minP[i * p[j]] = p[j];
        }
        if(1ll * i * minP[i] <= m){
            minP[i * minP[i]] = minP[i];
        }
    }
    for(int i = 1;i<=m;i++){
        pi[i] = (pi[i - 1] + (minP[i] == i));
    }
    
}
const __int128 one = 1;
struct hash1{
    size_t trs(long long x) const{
        x ^= x<<1;
        x ^= x<<5;
        x ^= (x<<7) & (x>>2);
        return x;
    }
    size_t trs1(int x) const{
        x ^= x<<2;
        x ^= x<<4;
        x ^= (x>>2) & (x<<3);
        return x;
    }
    size_t operator()(const pair<long long,int> &val) const{
        return trs(val.first) ^ trs1(val.second);
    }
};
unordered_map<pair<long long,int>,long long,hash1> mp;
long long queryg(long long n,int k){
    if(k == 0){
        return n - 1;
    }
    if(mp.count(make_pair(n,k))){
        return mp[make_pair(n,k)];
    }
    int sqn = sqrtl(n);
    if(k > pi[sqn]){
        if(n > m){
            int res = queryg(n,pi[sqn]) + pi[sqn] - k; 
            mp[make_pair(n,k)] = res;
            return res;
        }else{
            return pi[n] - k;
        }
    }
    long long sg = queryg(n,k - 1);
    long long res = p[k - 1];
    for(;res <= n;res*=p[k - 1]){
        sg -= 1;
        if(res * p[k - 1] <= n){
            sg -= queryg(n/res,k);
        }
    }
    mp[make_pair(n,k)] = sg;
    return sg;
}
signed main(){
    long long n;
    cin>>n;
    m = sqrtl(n);
    cerr<<m<<'\n';
    pre();
    long long res = queryg(n,pi[m])+ pi[m];   
    cout<<res<<'\n';
}